package top.jacktgq.hashmap;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @Author CandyWall
 * @Date 2020/11/6--17:03
 * @Description 模拟HashMap并发死链：
 *                  注意：必须在jdk1.7环境下模拟，否则扩容机制和hash的计算方法都变了
 *                     1、jdk1.7 HashMap中的链表采用的是头插入，而jdk1.8 HashMap中的采用的则是尾插法
 *                     2、并发死链发生在jdk1.7的多线程并发扩容的环节，而头插法也是并发死链情况出现的原因之一
 */
public class HashMapDeadLink {
    public static void main(String[] args) {
        //可以先调用此方法来了解一下key为1-64时的hash分布
        //calulateHash();
        //现有HashMap<Integer, Integer>，经过计算
        final HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        //HashMap容量为16时，key为1,16,35,50时，它们在一个桶内
        //HashMap容量为32时，key为1,35时，它们在一个桶内
        //HashMap中存放的元素个数超过容量的3/4时，会进行扩容
        //一开始HashMap的容量的初始值为16，它的扩容的条件为16*3/4=12，
        //因此先可以先存入12个元素，当存入13个元素时，它会扩容，然后容量翻倍，变成32
        //放12个元素
        map.put(2, null);
        map.put(3, null);
        map.put(4, null);
        map.put(5, null);
        map.put(6, null);
        map.put(7, null);
        map.put(8, null);
        map.put(9, null);
        map.put(10, null);
        //后三个元素会形成一条链
        map.put(16, null);
        map.put(35, null);
        map.put(1, null);
        System.out.println("扩容前大小[main]:"+map.size());

        //通过新建两个线程，同时向里面加入第13个元素，通过debug再现HashMap的并发死链问题
        new Thread() {
            @Override
            public void run() {
                // 放第 13 个元素, 发生扩容
                map.put(50, null);
                System.out.println("扩容后大小[Thread-0]:"+map.size());
            }
        }.start();
        new Thread() {
            @Override
            public void run() {
                // 放第 13 个元素, 发生扩容
                map.put(50, null);
                System.out.println("扩容后大小[Thread-1]:"+map.size());
            }
        }.start();
    }

    //计算1-64中hash值相等的值
    private static void calulateHash() {
        calculateSameHashKeyWithCapcity(16, 64);
        calculateSameHashKeyWithCapcity(32, 64);
    }

    //根据HashMap的容量，求出0~bound间所有的hash值相等的key

    /**
     *
     * @param capcity   ：HashMap的容量，必须是16的整数倍
     * @param bound     ：打印的key的最大值
     */
    private static void calculateSameHashKeyWithCapcity(int capcity, int bound) {
        if (capcity < 0 || capcity % 16 != 0) {
            throw new RuntimeException("传入的HashMap的容量必须大于0并且是16的整数倍！");
        }
        ArrayList<Integer>[] hashResults = new ArrayList[capcity];
        for (int i = 0; i < capcity; i++) {
            hashResults[i] = new ArrayList<Integer>();
            for (int j = 0; j < bound; j++) {
                if (hash(j) % capcity == i) {
                    hashResults[i].add(j);
                }
            }
        }
        for (int i = 0; i < hashResults.length; i++) {
            System.out.print("HashMap容量为" + capcity + "时，桶下标为 " + i + " 的key：");
            for (Integer key : hashResults[i]) {
                System.out.print(key + "->");
            }
            System.out.println("null");
        }
    }

    final static int hash(Object k) {
        int h = 0;
        /*if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }*/
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
}
